package leetcode.other.dynamic_programming;

/**
 * @Description: https://leetcode.cn/problems/longest-common-subsequence/
 * 给定两个字符串text1 和text2，返回这两个字符串的最长 公共子序列 的长度。
 *
 * 如果不存在 公共子序列 ，返回 0 。
 *
 * 一个字符串的子序列是指这样一个新的字符串：
 *
 * 它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 *
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 *
 * @Author Ammar
 * @Create 2023/7/5 21:32
 */
public class _1143_最长公共子序列 {

    /**
     * dp(i, j)表示nums1前i个元素与nums2前j个元素的最长公共序列长度
     * 动态规划状态方程：
     * 如果 nums1[i - 1] == nums2[j - 1]，dp(i,j) = dp(i-1,j-1) + 1
     * 如果 nums1[i - 1] != nums2[j - 1]，dp(i,j) = max{dp(i - 1, j), dp(i, j - 1)}
     */
    public static void main(String[] args) {
        int len = new _1143_最长公共子序列().lcs(new int[] {1, 4, 5, 9, 10}, new int[] {1, 4, 9, 10});
        System.out.println(len);
    }

    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text2 == null) return 0;
        if (text1.length() == 0 || text2.length() == 0) return 0;
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();

        char[] rowChars = chars1, colsChars = chars2;
        if (chars1.length < chars2.length) {
            rowChars = chars2;
            colsChars = chars1;
        }

        int[] dp = new int[colsChars.length + 1];
        for (char i = 1; i <= rowChars.length; i++) {
            int cur = 0;
            for (char j = 1; j <= colsChars.length; j++) {
                int topleft = cur;
                cur = dp[j];
                if (rowChars[i - 1] == colsChars[j - 1]) {
                    dp[j] = topleft + 1;
                } else {
                    // dp[j] = dp[i - 1][j]， dp[j-1] = dp[i][j-1]
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
            }
        }
        return dp[colsChars.length];
    }


    /**
     * 一维数组
     */
    public int lcs(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        int[] rowNums = nums1, colsNums = nums2;
        if (nums1.length < nums2.length) {
            rowNums = nums2;
            colsNums = nums1;
        }

        int[] dp = new int[colsNums.length + 1];
        for (int i = 1; i <= rowNums.length; i++) {
            int cur = 0;
            for (int j = 1; j <= colsNums.length; j++) {
                int topleft = cur;
                cur = dp[j];
                if (rowNums[i - 1] == colsNums[j - 1]) {
                    dp[j] = topleft + 1;
                } else {
                    // dp[j] = dp[i - 1][j]， dp[j-1] = dp[i][j-1]
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
            }
        }
        return dp[colsNums.length];
    }


    /**
     * 滚动数组
     */
    public int lcs4(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;

        int[][] dp = new int[2][nums2.length + 1];
        for (int i = 1; i <= nums1.length; i++) {
            int row = i & 1; // i % 2
            int prewRow = (i - 1) & 1;
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[row][j] = dp[prewRow][j - 1] + 1;
                } else {
                    dp[row][j] = Math.max(dp[prewRow][j], dp[row][j - 1]);
                }
            }
        }
        return dp[nums1.length & 1][nums2.length];
    }


    /**
     * 递推，滚动数组
     */
    public int lcs3(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;

        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }

    /**
     * 递推，二维数组
     * @param nums1
     * @param nums2
     * @return
     */
    public int lcs2(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;

        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }



    public int lcs1(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        return lcs1(nums1, nums1.length, nums2, nums2.length);
    }
    public int lcs1(int[] nums1, int i, int[] nums2, int j) {
        // 初始条件
        if (i == 0 || j == 0) return 0;
        if (nums1[i - 1] == nums2[j - 1]) {
            return lcs1(nums1, i - 1, nums2, j - 1) + 1;
        } else {
            return Math.max(lcs1(nums1, i - 1, nums2, j), lcs1(nums1, i, nums2, j - 1));
        }
    }

}
